#ifndef _CUBE_H
#define _CUBE_H

class Cube
{
public:
	struct TheCube
	{
		TheCube() {left=nullptr; right=nullptr; x=0; y=0; z=0; width=0; height=0; depth=0;};
		TheCube *left;
		TheCube *right;

		int x;
		int y;
		int z;
		int width;
		int height;
		int depth;
	};

	void Init(int width, int height, int depth)
	{
		root.left = root.right = nullptr;
		root.x = root.y = root.z = 0;
		root.width = width;
		root.depth = depth;
		root.height = height;
	}

private:

	TheCube root;

	TheCube *Insert(TheCube *theCube, int width, int height, int depth)
	{
		if (theCube->left || theCube->right)
		{
			if (theCube->left)
			{
				TheCube *newCube = Insert(theCube->left, width, height, depth);
				if (newCube)
					return newCube;
			}
			if (theCube->right)
			{
				TheCube *newCube = Insert(theCube->right, width, height, depth);
				if (newCube)
					return newCube;
			}
			return 0;
		}

		if (width > theCube->width || height > theCube->height || depth > theCube->depth)
			return 0;

		int w = theCube->width - width;
		int h = theCube->height - height;
		int d = theCube->depth - depth;
		theCube->left = new TheCube;
		theCube->right = new TheCube;
		if (w <= h && w <= d)
		{
			theCube->left->x = theCube->x + width;
			theCube->left->y = theCube->y;
			theCube->left->z = theCube->z;
			theCube->left->width = w;
			theCube->left->height = height;
			theCube->left->depth = depth;

			theCube->right->x = theCube->x;
			theCube->right->y = theCube->y + height;
			theCube->right->z = theCube->z + depth;
			theCube->right->width = theCube->width;
			theCube->right->height = h;
			theCube->right->depth = d;
		}
		else
		{
			theCube->left->x = theCube->x;
			theCube->left->y = theCube->y + height;
			theCube->left->z = theCube->z
			theCube->left->width = width;
			theCube->left->height = h;
			theCube->left->depth = depth;

			theCube->right->x = theCube->x + width;
			theCube->right->y = theCube->y;
			theCube->right->z = theCube->z + depth;
			theCube->right->width = w;
			theCube->right->height = theCube->height;
			theCube->right->depth = d;
		}

		theCube->width = width;
		theCube->height = height;
		theCube->depth = depth;
		return theCube;

	Cube(void);
	~Cube(void);
};

#endif //_CUBE_H